1. Field of Invention
This invention relates to a method for improving a scheduler (also called an arbiter). More particularly this method can limit the rate at which an arbiter can render an arbitration decision to the same party. This invention is particularly advantageous for implementation in digital computer hardware. The primary application of current interest is to circuit based schedulers that manage traffic in high-speed switches and routers. However, the technique may be useful in a variety of applications involving input data that is stored and then retrieved based on the priority of Service Tags. Consequently, data retrieved arbitrates between the data stored. The data stored may be considered as separate flows each contending for the retrieval resource. Often times, a particular application needs to limit the rate at which one party, or flow, is selected by the scheduler. This is useful for preventing the downstream congestion of another resource specific to the over-selected flow, or for enforcing service contracts for particular flows.
A very useful application of this invention is in construction of devices which participate in Internet Protocol (IP) networks or Asynchronous Transfer Mode (ATM) networks. The following discussion reviews how the features of an arbitration scheme can lead to “rich networking services” or traffic management, and how this invention's arbitration enhancement provides better traffic management.
At every point of contention in a network, packets or cells must be prioritized to ensure Service Level Agreements (SLA). Underlying, identified flows often serve as the prioritization criterion. This re-ordering of packets modifies the traffic shape of these flows and requires a buffer.
The scheduling discipline chosen for this prioritization, or Traffic Management (TM), can affect the traffic shape of flows and micro-flows through: Delay (buffering); Bursting of traffic (buffering and bursting); Smoothing of traffic (buffering and rate-limiting flows); Dropping traffic (choosing data to discard so as to avoid exhausting the buffer); Delay jitter (temporally shifting cells of a flow by different amounts); Not admitting a connection (cannot simultaneously guarantee existing SLAs with an additional flow's SLA).
In current non-centralized router architectures, the TM provided by the switch fabric consists of a small number of depth-limited queues of strict priority. Therefore, the TM on the ingress and egress of each line card must carry the burden of enforcing SLAs. This includes providing the agreed upon data-rate and not providing more than the maximum data-rate.
2. Prior Art
The standard method of rate limiting involves marking each individual flow as In-Profile or Out-of-Profile. This marking has to be done continuously as flows go from over the maximum data-rate to under the agreed upon data-rate (and vice-versa) as time progresses. As such, the amount of new information to be processed in the scheduling decision can be commensurate with the number of flows: if all the flows change their current profile, all that information must be factored into the scheduling decision.
This invention serves to reduce the amount of profile-related information flux inputted to the scheduler, and so it increases the speed of the scheduler or the number of flows the scheduler can arbitrate at the same speed. This is because a simple circuit scheduler (one incapable of rate-limiting) is conventionally faster than a circuit scheduler that must schedule and rate limit at the same time. This increase in performance is very useful in the traffic management of networks.